package zuo.from0516.basic2020.class01;

/**
 * 局部最小值问题。无序数组（正负0）任意相邻的两个数不相等，
 * 若0位置<1位置或n-2位置大于n-1位置，或i位置小于i －1位置且小于i +1位置，
 * 则有局部最小值，找出一个局部最小值。
 */
public class Code06_BSAwesome {
    public static int getLessIndex(int[] arr){
        int ans = -1;
        if(arr.length <2){
            return ans;
        }
        if(arr.length == 2 && arr[0]<arr[1]){
            return arr[0];
        }
        if(arr[arr.length-2]>arr[arr.length-1]){
            return arr[arr.length-1];
        }
        int L =1,R =arr.length -2;
        while(L < R){
            int mid = L + ((R-L)>>1);
            if(arr[mid] > arr[mid-1]){
                R = mid-1;
            }else if(arr[mid]>arr[mid+1]){
                L = mid+1;
            }else {
                ans = mid;
                return arr[ans];
            }
        }
        return arr[L];
    }

    public static int getLessIndexRight(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
    public static void main(String[] args) {
        int[] arr = {11,10,8,7,4,6,9};
        int lessIndex = getLessIndex(arr);
        System.out.println(lessIndex);
    }
}
